SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Jenkins hash function</title>

</head>

Jenkins hash function

</h1>

</header>

The Jenkins hash functions are a family of <a href="Non-cryptographic_hash_function" title="Non-cryptographic hash function">non-cryptographic hash functions</a> for multi-<a href="Byte" title="Byte">byte</a> keys designed by <a href="Robert_John_Jenkins_Junior" class="mw-redirect" title="Robert John Jenkins Junior">Bob Jenkins</a>. The first one was formally published in 1997.

<div class="mw-heading mw-heading2"><h2 id="The_hash_functions">The hash functions</h2></div>

Jenkins's one_at_a_time hash is adapted here from a WWW page by Bob Jenkins,<a href="#cite_note-dobbsx-1">[1]</a> which is an expanded version of his <a href="Dr._Dobb's_Journal" title="Dr. Dobb's Journal">Dr. Dobb's</a> article.<a href="#cite_note-dobbs-2">[2]</a> It was originally created to fulfill certain requirements described by Colin Plumb, a cryptographer, but was ultimately not put to use.<a href="#cite_note-dobbsx-1">[1]</a>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {

size_t i = 0;

uint32_t hash = 0;

while (i != length) {

hash += key[i++];

hash += hash << 10;

hash ^= hash >> 6;

}

return hash;

}

</pre></div>

Sample hash values for one_at_a_time hash function.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>one_at_a_time("a", 1)

0xca2e9442

one_at_a_time("The quick brown fox jumps over the lazy dog", 43)

0x519e91f5

</pre></div>

The <a href="Avalanche_effect" title="Avalanche effect">avalanche</a> behavior of this hash is shown on the right.

Each of the 24 rows corresponds to a single bit in the 3-byte input key, and each of the 32 columns corresponds to a bit in the output hash. Colors are chosen by how well the input key bit affects the given output hash bit: a green square indicates good mixing behavior, a yellow square weak mixing behavior, and red would indicate no mixing. Only a few bits in the last byte of the input key are weakly mixed to a minority of bits in the output hash.

Standard implementations of the <a href="Perl" title="Perl">Perl</a> programming language prior to version 5.28 included Jenkins's one-at-a-time hash or a hardened variant of it, which was used by default.<a href="#cite_note-3">[3]</a><a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading3"><h3 id="lookup2">lookup2</h3></div>

The lookup2 function was an interim successor to one-at-a-time. It is the function referred to as "My Hash" in the 1997 Dr. Dobbs journal article, though it has been obsoleted by subsequent functions that Jenkins has released. Applications of this hash function are found in:

<ul><li>the <a href="SPIN_model_checker" title="SPIN model checker">SPIN model checker</a>, for probabilistic error detection. In a paper about this program, researchers Dillinger and Manolios note that lookup2 is "a popular choice among implementers of hash tables and <a href="Bloom_filter" title="Bloom filter">Bloom filters</a>". They study lookup2 and a simple extension of it that produces 96-bit rather than 32-bit hash values.<a href="#cite_note-5">[5]</a></li>

<li>The <a href="Netfilter" title="Netfilter">Netfilter</a> firewall component of <a href="Linux_kernel" title="Linux kernel">Linux</a>,<a href="#cite_note-6">[6]</a> where it replaced an earlier hash function that was too sensitive to collisions. The resulting system, however, was shown to still be sensitive to <a href="Hash_flooding" class="mw-redirect" title="Hash flooding">hash flooding</a> attacks, even when the Jenkins hash is randomized using a secret key.<a href="#cite_note-7">[7]</a></li>

<li>The program that solved the game of <a href="Kalah" title="Kalah">kalah</a> used the Jenkins hash function, instead of the <a href="Zobrist_hashing" title="Zobrist hashing">Zobrist hashing</a> technique more commonly used for this type of problem; the reasons for this choice were the speed of Jenkins' function on the small representations of kalah boards, as well as the fact that the basic rule of kalah can radically alter the board, negating the benefit of Zobrist's incremental computation of hash functions.<a href="#cite_note-8">[8]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="lookup3">lookup3</h3></div>

The lookup3 function consumes input in 12 byte (96 bit) chunks.<a href="#cite_note-9">[9]</a> It may be appropriate when speed is more important than simplicity. Note, though, that any speed improvement from the use of this hash is only likely to be useful for large keys, and that the increased complexity may also have speed consequences such as preventing an optimizing compiler from inlining the hash function.

The lookup3 function was incorporated into <a href="Hierarchical_Data_Format" title="Hierarchical Data Format">Hierarchical Data Format 5</a> as a checksum for internal data structures based on its relative strength and speed in comparison to <a href="CRC-32" class="mw-redirect" title="CRC-32">CRC-32</a> and <a href="Fletcher's_checksum#Fletcher-32" title="Fletcher's checksum">Fletcher-32</a>.

<div class="mw-heading mw-heading3"><h3 id="SpookyHash">SpookyHash</h3></div>

In 2011 Jenkins released a new 128-bit hash function called SpookyHash.<a href="#cite_note-11">[11]</a> SpookyHash is significantly faster than lookup3.

Example for V2 (little-endian x64):

The short method for less than 192 bytes (43 bytes):

<pre>Hash128("The quick brown fox jumps over the lazy dog")

2b12e846aa0693c71d367e742407341b

</pre>

The standard method for more than 191 bytes (219 bytes):

<pre>Hash128("The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog")

f1b71c6ac5af39e7b69363a60dd29c49

</pre>

<ul><li><a href="Non-cryptographic_hash_functions" class="mw-redirect" title="Non-cryptographic hash functions">Non-cryptographic hash functions</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJenkins2013" class="citation web cs1">Jenkins, Bob (November 3, 2013). <a rel="nofollow" class="external text" href="http://www.burtleburtle.net/bob/hash/doobs.html">"A hash function for hash Table lookup"</a>. Retrieved February 9, 2018.</cite>

</li>

<li id="cite_note-dobbs-2"><a href="#cite_ref-dobbs_2-0">^</a> <cite id="CITEREFJenkins1997" class="citation journal cs1">Jenkins, Bob (September 1997). <a rel="nofollow" class="external text" href="https://www.drdobbs.com/database/algorithm-alley/184410284">"Hash functions"</a>. Dr. Dobb's Journal.</cite>

</li>

<a rel="nofollow" class="external text" href="http://www.perlmonks.org/?node_id=381061">"RFC: perlfeaturedelta"</a>:

"one-at-a-time hash algorithm ... [was added in version] 5.8.0"

</li>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFDillingerManolios2004" class="citation conference cs1">Dillinger, Peter C.; Manolios, Panagiotis (2004). Fast and accurate bitstate verification for SPIN. Proc. 11th International SPIN Workshop. pp. 57–75. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6765">10.1.1.4.6765</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFNeira_Ayuso2006" class="citation journal cs1">Neira Ayuso, Pablo (2006). <a rel="nofollow" class="external text" href="http://static.usenix.org/publications/login/2006-06/pdfs/neira.pdf">"Netfilter's connection tracking system"</a> (PDF). <a href="%3Blogin%3A" title=";login:">;login:</a>. 31 (3).</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFBar-YosefWool2007" class="citation conference cs1">Bar-Yosef, Noa; Wool, Avishai (2007). <a rel="nofollow" class="external text" href="https://www.eng.tau.ac.il/~yash/C2_039_Wool.pdf">Remote algorithmic complexity attacks against randomized hash tables Proc. International Conference on Security and Cryptography (SECRYPT)</a> (PDF). pp. 117–124.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFIrvingDonkersUiterwijk" class="citation journal cs1">Irving, Geoffrey; Donkers, Jeroen; Uiterwijk, Jos. <a rel="nofollow" class="external text" href="https://naml.us/~irving/papers/irving2000_kalah.pdf">"Solving kalah"</a> (PDF). <a href="ICGA_Journal" title="ICGA Journal">ICGA Journal</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFJenkins" class="citation web cs1">Jenkins, Bob. <a rel="nofollow" class="external text" href="http://www.burtleburtle.net/bob/c/lookup3.c">"lookup3.c source code"</a>. Retrieved April 16, 2009.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFKoziol" class="citation web cs1">Koziol, Quincey. <a rel="nofollow" class="external text" href="https://github.com/HDFGroup/hdf5/commit/d3a12e1058e9afcb77b265a88690f1d3d5190fd7">"[svn-r12661] Description: · HDFGroup/hdf5@d3a12e1"</a>. Retrieved July 18, 2023.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFJenkins" class="citation web cs1">Jenkins, Bob. <a rel="nofollow" class="external text" href="http://www.burtleburtle.net/bob/hash/spooky.html">"SpookyHash: a 128-bit noncryptographic hash"</a>. Retrieved Jan 29, 2012.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-04" href="https://en.wikipedia.org/wiki/?title=Jenkins_hash_function&oldid=1298760136">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>